package haxe.util;

typedef QEntry = {
	var next:QEntry;
	var value:Dynamic;
}

class Queue<T> implements Collection<T>
{
	public var head(getHead,null):T;
	public var tail(getTail,null):T;
	public var size(getSize,null):Int;
	
	private var _s:Int;
	private var _head:QEntry;
	private var _tail:QEntry;
	
	public function new()
	{
		this._s = 0;
		this._head = this._tail = { next:null, value:null };
	}
	
	public function add(o:T):Void
	{
		this.enqueue(o);
	}
	
	public function addAll(c:Collection<T>):Void
	{
		for( i in c )
			add(i);
	}
	
	public function remove(o:T, ?equals: T->T->Bool):Bool
	{
		if ( this._s > 1 )
		{
			var e:QEntry = this._head;
			var prev:QEntry = null;
			while ( e.next != null && e.value != o )
			{
				prev = e;
				e = e.next;
			}
			if ( e.value == o )
			{
				if( prev != null )
				{
					prev.next = e.next;
				}else{
					this._head = e.next;
				}
				--_s;
				return true;
			}else
				return false;
		}
		else if ( _s == 1 && this._head.value == o )
		{
			this._head = _tail = null;
			_s = 0;
			return true;
		}else
			return false;
	}
	
	public function removeAll(c:Collection<T>, ?equals: T->T->Bool):Bool
	{
		var r:Bool = false;
		for ( i in c )
		{
			if ( this.remove(i) && !r ) r = true;
		}
		return r;
	}
	
	public function enqueue( o:T ):Void
	{
		if ( this._s > 0 )
		{
		this._tail = ( this._tail.next = { next:null, value:o } );
		}
		else
		{
			this._head = this._tail = { next:null, value:o };
		}
		++this._s;
	}
	
	public function dequeue():T
	{
		var r:T = null;
		if ( this._s > 0 )
		{
			r = _head.value;
			this._head = this._head.next;
			--this._s;//_s = if( _s > 0 ) _s - 1 else 0;
		}
		return r;
	}
	
	public function isEmpty():Bool
	{
		return _s == 0;
	}
	
	public function clear():Void
	{
		_head = null;
		_tail = null;
		_s = 0;
	}
	
	public function contains(o:T, ?equals: T->T->Bool ):Bool
	{
		if ( this._s == 0 )
			return false;
		var e:QEntry = this._head;
		while( e.next != null && e.value != o  )
		{
			e = e.next;
		}
		return ( e.value == o );
	}
	
	public function containsAll(c:Collection<T>, ?equals: T->T->Bool ):Bool
	{
		if ( this._s < c.size )
			return false;
		for ( i in c )
		{
			if ( ! contains(i) )
				return false;
		}
		return true;
	}
	
	public function iterator():Iterator<T>
	{
		return new QueueIterator(_head);
	}
	
	public function toArray():Array<T>
	{
		var _a:Array<T> = new Array();
		var it:QEntry = _head;
		while( it != null )
		{
			_a.push(it.value);
			it = it.next;
		}
		return _a;
	}
	
	private function getHead():T
	{
		return _head.value;
	}
	
	private function getTail():T
	{
		return _tail.value;
	}
	
	private function getSize():Int
	{
		return _s;
	}
}

class QueueIterator<T>
{
	private var _e:QEntry;
	
	public function new( h:QEntry )
	{
		_e = {next:h,value:null};
	}
	public function hasNext() 
	{
		return _e.next != null;
	}

	public function next():T
	{
		_e = _e.next;
		return _e.value;
	}
}
